<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  <title>红黑树的实现原理及应用 | Zhaoxi Blooooooooog</title>
  <meta name="keywords" content=" 红黑树 ">
  <meta name="description" content="红黑树的实现原理及应用 | Zhaoxi Blooooooooog">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="前言最近在重构代码, 为框架添加Autofac作为ioc容器, 在处理业务层时, 遇到不同Service相互依赖的问题, 俗称循环依赖. 后来经过讨论解决了这个问题, 这里记录一下我们的探索过程. 场景介绍A服务依赖于B服务作为构造函数的参数, B服务依赖于A服务作为构造函数的参数, demo代码如下:     public class ServiceA : IServiceA     {">
<meta name="keywords" content="ioc,循环依赖">
<meta property="og:type" content="article">
<meta property="og:title" content="ioc循环依赖的发现与解决">
<meta property="og:url" content="https://zhaoxiwork.gitee.io/zhaoxiwork.gitee.io/2019/09/16/ioc循环依赖的发现与解决/index.html">
<meta property="og:site_name" content="Zhaoxi Blooooooooog">
<meta property="og:description" content="前言最近在重构代码, 为框架添加Autofac作为ioc容器, 在处理业务层时, 遇到不同Service相互依赖的问题, 俗称循环依赖. 后来经过讨论解决了这个问题, 这里记录一下我们的探索过程. 场景介绍A服务依赖于B服务作为构造函数的参数, B服务依赖于A服务作为构造函数的参数, demo代码如下:     public class ServiceA : IServiceA     {">
<meta property="og:locale" content="zn-CN">
<meta property="og:updated_time" content="2019-09-18T13:14:07.356Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="ioc循环依赖的发现与解决">
<meta name="twitter:description" content="前言最近在重构代码, 为框架添加Autofac作为ioc容器, 在处理业务层时, 遇到不同Service相互依赖的问题, 俗称循环依赖. 后来经过讨论解决了这个问题, 这里记录一下我们的探索过程. 场景介绍A服务依赖于B服务作为构造函数的参数, B服务依赖于A服务作为构造函数的参数, demo代码如下:     public class ServiceA : IServiceA     {">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.0.1" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.0.1" rel="stylesheet">

<link href="//cdn.bootcss.com/animate.css/3.5.2/animate.min.css" rel="stylesheet">
<link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">

<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
<script src="/js/jquery.autocomplete.min.js?v=1.0.1"></script>

<script src="//cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.bootcss.com/nprogress/0.2.0/nprogress.min.js"></script>



<script src="//cdn.bootcss.com/jquery-cookie/1.4.1/jquery.cookie.min.js"></script>

<script src="/js/iconfont.js?v=1.0.1"></script>

</head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="false">
  <input class="theme_blog_path" value>
</div>

<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>Zhaoxi</span>
</div>

<div class="icon">
    
        
        <a title="github" href="https://github.com/zhao4xi" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-github"></use>
                </svg>
            
        </a>
        
    
        
        <a title="email" href="mailto:zhao4xi@126.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=517810353&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active">全部文章<small>(21)</small></div></li>
    
        
            
            <li><div data-rel="数据库">数据库<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Redis">Redis<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Spring">Spring<small>(4)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="协议">协议<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Java">Java<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="框架">框架<small>(1)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="算法">算法<small>(1)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a  class="friends">友链</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="21">
<input type="hidden" id="yelog_site_word_count" value="24.4k">
<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        友情链接
        <i class="back-title-list"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <form onkeydown="if(event.keyCode==13){return false;}">
        <input class="search" type="text" placeholder="以 in: 开头进行全文搜索" autocomplete="off"id="local-search-input" >
        <i class="cross"></i>
        <span>
            <label for="tagswitch">Tags:</label>
            <input id="tagswitch" type="checkbox" style="display: none" />
            <i id="tagsWitchIcon"></i>
        </span>
    </form>
    <div class="tags-list">
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">MySQL</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">锁</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">redis</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color5">lock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">spring</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">transaction</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">bean scope</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Spring</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">tcp</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">spring mvc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">ThreadLocal</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color5">http</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">https</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">ioc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color5">循环依赖</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">aop</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">volatile</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Thread Safe</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">Collection</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Thread</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Thread Pool</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">红黑树</a>
    </li>
    
    <div class="clearfix"></div>
</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a  class="数据库 "
           href="/zhaoxiwork.gitee.io/2018/12/14/MySQL字段到底推不推荐使用null值/"
           data-tag="MySQL"
           data-author="" >
            <span class="post-title" title="MySQL字段到底推不推荐使用null值">MySQL字段到底推不推荐使用null值</span>
            <span class="post-date" title="2018-12-14 14:59:38">2018/12/14</span>
        </a>
        
        <a  class="数据库 "
           href="/zhaoxiwork.gitee.io/2019/01/03/Mysql实现乐观锁和悲观锁/"
           data-tag="MySQL,锁"
           data-author="" >
            <span class="post-title" title="MySQL实现乐观锁和悲观锁">MySQL实现乐观锁和悲观锁</span>
            <span class="post-date" title="2019-01-03 14:58:25">2019/01/03</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2018/12/31/Redis为什么这么快之数据结构/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis为什么这么快之数据结构">Redis为什么这么快之数据结构</span>
            <span class="post-date" title="2018-12-31 15:15:35">2018/12/31</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2019/01/03/Redis实现分布式锁/"
           data-tag="redis,lock"
           data-author="" >
            <span class="post-title" title="Redis实现分布式锁">Redis实现分布式锁</span>
            <span class="post-date" title="2019-01-03 15:17:22">2019/01/03</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2019/01/01/Redis为什么这么快之服务器事件驱动/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis为什么这么快之服务器事件驱动">Redis为什么这么快之服务器事件驱动</span>
            <span class="post-date" title="2019-01-01 15:16:15">2019/01/01</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2018/12/30/Redis的数据持久化方式/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis的数据持久化方式">Redis的数据持久化方式</span>
            <span class="post-date" title="2018-12-30 15:14:47">2018/12/30</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2018/12/29/Redis的数据类型和基本使用/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis的数据类型和基本使用">Redis的数据类型和基本使用</span>
            <span class="post-date" title="2018-12-29 15:13:48">2018/12/29</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2019/01/05/Spring-事务/"
           data-tag="spring,transaction"
           data-author="" >
            <span class="post-title" title="Spring 事务">Spring 事务</span>
            <span class="post-date" title="2019-01-05 14:49:55">2019/01/05</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2018/12/26/Spring-Bean的作用域和生命周期/"
           data-tag="bean scope,Spring"
           data-author="" >
            <span class="post-title" title="Spring Bean的作用域和生命周期">Spring Bean的作用域和生命周期</span>
            <span class="post-date" title="2018-12-26 15:09:21">2018/12/26</span>
        </a>
        
        <a  class="协议 "
           href="/zhaoxiwork.gitee.io/2019/01/05/TCP-IP的三次握手和四次挥手/"
           data-tag="tcp"
           data-author="" >
            <span class="post-title" title="TCP/IP的三次握手和四次挥手">TCP/IP的三次握手和四次挥手</span>
            <span class="post-date" title="2019-01-05 14:51:46">2019/01/05</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2018/12/27/Spring-MVC的请求处理流程/"
           data-tag="spring mvc"
           data-author="" >
            <span class="post-title" title="Spring MVC的请求处理流程">Spring MVC的请求处理流程</span>
            <span class="post-date" title="2018-12-27 15:11:12">2018/12/27</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/23/ThreadLocal使用场景及内存泄漏/"
           data-tag="ThreadLocal"
           data-author="" >
            <span class="post-title" title="ThreadLocal使用场景及内存泄漏">ThreadLocal使用场景及内存泄漏</span>
            <span class="post-date" title="2018-12-23 15:03:24">2018/12/23</span>
        </a>
        
        <a  class="协议 "
           href="/zhaoxiwork.gitee.io/2019/01/28/https和http的区别与比较/"
           data-tag="http,https"
           data-author="" >
            <span class="post-title" title="https和http的区别与比较">https和http的区别与比较</span>
            <span class="post-date" title="2019-01-28 09:37:25">2019/01/28</span>
        </a>
        
        <a  class="框架 "
           href="/zhaoxiwork.gitee.io/2019/09/16/ioc循环依赖的发现与解决/"
           data-tag="ioc,循环依赖"
           data-author="" >
            <span class="post-title" title="ioc循环依赖的发现与解决">ioc循环依赖的发现与解决</span>
            <span class="post-date" title="2019-09-16 10:30:51">2019/09/16</span>
        </a>
        
        <a  class=""
           href="/zhaoxiwork.gitee.io/2019/09/15/hello-world/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Hello World">Hello World</span>
            <span class="post-date" title="2019-09-15 22:07:00">2019/09/15</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2018/12/25/spring中的两种aop实现方式jdk动态代理和cglib代理/"
           data-tag="spring,aop"
           data-author="" >
            <span class="post-title" title="spring中的两种aop实现方式jdk动态代理和cglib代理">spring中的两种aop实现方式jdk动态代理和cglib代理</span>
            <span class="post-date" title="2018-12-25 15:07:32">2018/12/25</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/23/volatile的使用方法及一些注意事项/"
           data-tag="volatile"
           data-author="" >
            <span class="post-title" title="volatile的使用方法及一些注意事项">volatile的使用方法及一些注意事项</span>
            <span class="post-date" title="2018-12-23 15:04:16">2018/12/23</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/17/如何实现线程安全/"
           data-tag="Thread Safe"
           data-author="" >
            <span class="post-title" title="如何实现线程安全">如何实现线程安全</span>
            <span class="post-date" title="2018-12-17 15:01:54">2018/12/17</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/24/常用Map的比较与实现-jdk1-8/"
           data-tag="Collection"
           data-author="" >
            <span class="post-title" title="常用Map的比较与实现(jdk1.8+)">常用Map的比较与实现(jdk1.8+)</span>
            <span class="post-date" title="2018-12-24 15:05:34">2018/12/24</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/15/深入理解Java线程池/"
           data-tag="Thread,Thread Pool"
           data-author="" >
            <span class="post-title" title="深入理解Java线程池">深入理解Java线程池</span>
            <span class="post-date" title="2018-12-15 15:00:51">2018/12/15</span>
        </a>
        
        <a  class="算法 "
           href="/zhaoxiwork.gitee.io/2018/12/29/红黑树的实现原理及应用/"
           data-tag="红黑树"
           data-author="" >
            <span class="post-title" title="红黑树的实现原理及应用">红黑树的实现原理及应用</span>
            <span class="post-date" title="2018-12-29 15:12:44">2018/12/29</span>
        </a>
        
    </nav>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div class="post">
    <div class="pjax">
        <article id="post-红黑树的实现原理及应用" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">红黑树的实现原理及应用</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            
                <a href="javascript:" data-rel="算法">算法</a>
            
        </span>
        
        
        <span class="tag">
            
            <a href="javascript:" class="color4">红黑树</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
        创建时间:<time class="date" title='更新时间: 2019-09-21 15:24:34'>2018-12-29 15:12</time>
        
    </div>
    <div class="article-meta">
        
        <span>字数:2k</span>
        
        
        <span id="busuanzi_container_page_pv">
            阅读:<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#什么是红黑树"><span class="toc-text">什么是红黑树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#红黑树的应用和时间复杂度"><span class="toc-text">红黑树的应用和时间复杂度</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#红色树的操作"><span class="toc-text">红色树的操作</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#节点的基本定义"><span class="toc-text">节点的基本定义</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#旋转-左旋转的两种情况"><span class="toc-text">旋转 - 左旋转的两种情况</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#旋转-右旋转的两种情况"><span class="toc-text">旋转 - 右旋转的两种情况</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#插入并修正"><span class="toc-text">插入并修正</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#删除并修正"><span class="toc-text">删除并修正</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#完整实现"><span class="toc-text">完整实现</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考文献"><span class="toc-text">参考文献</span></a></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-3 i,
    .toc-level-3 ol {
        display: none !important;
    }
</style>
</div>
    <div class="article-entry" itemprop="articleBody">
      
        <p>@<a href="红黑树的实现原理及应用">OTC</a></p>
<h2 id="什么是红黑树"><a href="#什么是红黑树" class="headerlink" title="什么是红黑树"></a>什么是红黑树</h2><p>红黑树(R-B Tree, 全称 Red-Black Tree)是一种特殊的二叉查找树, 其中每个节点都有颜色, 红色或者黑色.<br>红黑树的特性:</p>
<ol>
<li>树的节点是黑色或者红色</li>
<li>树的根节点和指向null的叶子节点都是黑色</li>
<li>不能有两个红色节点是连续的</li>
<li>每个节点至为null的子节点的任何路径, 都含有相同数量的黑色节点</li>
</ol>
<p>示例:</p>
<pre><code class="java">             8B
            / \
           4R  9B
          /  \
        2B    6B
       /  \   / \
      1R  3R 5R  7R</code></pre>
<h2 id="红黑树的应用和时间复杂度"><a href="#红黑树的应用和时间复杂度" class="headerlink" title="红黑树的应用和时间复杂度"></a>红黑树的应用和时间复杂度</h2><ol>
<li>主要是 Java 中的 TreeMap 和 TreeSet. jdk1.8 之后, HashMap 的table中的链表长度大于8的时候也是用 红黑树.</li>
<li>时间复杂度: 查找, 插入, 删除都可以在 O(log n) 内完成. 且节点数为 n 的数高度最大为 2log(n+1).</li>
</ol>
<h2 id="红色树的操作"><a href="#红色树的操作" class="headerlink" title="红色树的操作"></a>红色树的操作</h2><h4 id="节点的基本定义"><a href="#节点的基本定义" class="headerlink" title="节点的基本定义"></a>节点的基本定义</h4><pre><code class="java">    //节点定义
    public class RBTNode&lt;T extends Comparable&lt;T&gt;&gt; {
        public boolean isBlack;
        public T key;
        public RBTNode&lt;T&gt; parent;
        public RBTNode&lt;T&gt; left;
        public RBTNode&lt;T&gt; right;

        public RBTNode(T key, RBTNode&lt;T&gt; parent, RBTNode&lt;T&gt; left, RBTNode&lt;T&gt; right, boolean isBlack) {
            this.isBlack = isBlack;
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public String toString() {
            return &quot;key: &quot; + key + (isBlack ? &quot; B &quot; : &quot; R &quot;) +
                    (parent != null ? (
                            ((parent.left != null &amp;&amp; parent.left == this) ?
                                    parent.key + &quot; Left&quot; :
                                    (parent.right != null &amp;&amp; parent.right == this) ?
                                    parent.key + &quot; Right&quot; : &quot;&quot;))
                            : &quot;&quot;);
        }
    }</code></pre>
<h4 id="旋转-左旋转的两种情况"><a href="#旋转-左旋转的两种情况" class="headerlink" title="旋转 - 左旋转的两种情况"></a>旋转 - 左旋转的两种情况</h4><p>旋转的中心思想是: 从新设置 x 节点, y 节点的 左 父 右 节点, 并设置关联变化的节点的父节点.</p>
<pre><code class="java">    px                   px             |                px                    px                     
     \                    \             |               /                     /                  
      x                    y            |              x           -&gt;        y                                 
     / \      -&gt;          / \           |             / \                   / \                       
   lx   y                x  ry          |            lx  y                 x   ry                        
       / \              / \             |               / \               / \                           
     ly  ry            lx  ly           |              ly  ry            lx ly                       

    // 对 x 进行左旋转, 将 x 是 y 的父节点变成, y 是 x 的父节点.
    private void rotateLeft(RBTNode&lt;T&gt; x) {
        RBTNode&lt;T&gt; y = x.right;
        // 1. 设置x 的 左 父 右 节点
        // 1-1 x的左节点无变化
        // 1-2 x的右节点, 设置x右节点的父节点
        x.right = y.left;
        if(y.left != null) y.left.parent = x;
        // 1-3 x的父节点无变化

        //2. 设置y 的 左 父 右 节点
        //2-1: 设置y的父节点
        y.parent = x.parent;

        if (x.parent == null) this.root = y;
        else if (x.parent.left == x) x.parent.left = y;
        else x.parent.right = y;

        //2-2: 设置y 的左节点
        y.left = x;
        x.parent = y;

        //2-3: y节点的右节点无变化
    }
</code></pre>
<h4 id="旋转-右旋转的两种情况"><a href="#旋转-右旋转的两种情况" class="headerlink" title="旋转 - 右旋转的两种情况"></a>旋转 - 右旋转的两种情况</h4><pre><code class="java">          py                py         |              py                   py           
         /                 /           |               \                    \         
        y                 x            |                y        -&gt;          x        
       / \        -&gt;     / \           |               / \                  / \       
      x   ry           lx   y          |              x  ry               lx   y      
     / \                   / \         |             / \                      / \     
    lx rx                 rx  ry       |            lx rx                    rx  ry   

    // 对 y 进行右旋转, 将 y 是 x 的父节点 变成 x 是 y 的父节点                                                                                                                  
    private void rotateRight(RBTNode&lt;T&gt; y) {
        RBTNode&lt;T&gt; x = y.left;

        //1: 设置y 的左 父 右 节点
        //1-1: 设置y 的左节点, 并设置其父节点
        y.left = x.right;
        if (x.right != null) x.right.parent = y;

        //2-2: 设置x的父节点
        x.parent = y.parent;
        //1-3: y的右节点无变化

        //2: 设置x 的左 右 父节点

        //2-2: 设置x 的父节点, 及其父节点的子节点
        if (y.parent == null) this.root = x;
        else if (y == y.parent.right) y.parent.right = x;
        else y.parent.left = x;

        //2-1: 设置 x的右节点, 并设置其父节点
        x.right = y;
        //1-2: 设置y 的父节点
        y.parent = x;
        //2-3 x的左节点无变化
    }
</code></pre>
<h4 id="插入并修正"><a href="#插入并修正" class="headerlink" title="插入并修正"></a>插入并修正</h4><ol>
<li>若root 是null , 则插入节点就是root 节点.</li>
<li>若root 不是null, 则向下查找node 的父节点, 并根据与父节点的大小关系, 写入待插入节点. 插入的节点都是红色</li>
<li>修正插入的树.</li>
<li>修正过程, 修正的核心思想是: 将红色节点移动到根节点, 将根节点设为黑色.</li>
</ol>
<table>
<thead>
<tr>
<th align="center">违背原则4</th>
<th align="left">现象说明</th>
<th align="left">处理策略</th>
</tr>
</thead>
<tbody><tr>
<td align="center">情况1</td>
<td align="left">isRed(parent), isRed(uncle)</td>
<td align="left">1. setBlack(parent);<br> 2. setBlack(uncle); <br>3. setRed(grandParent);<br> 4. current = grandParent;<br>5. 检测 current 是否违背原则并处理</td>
</tr>
<tr>
<td align="center">情况2</td>
<td align="left">isRed(parent), isBlack(uncle), uncle == grandParent.left, current == parent.right</td>
<td align="left">1. setBlack(parent);<br> 2. setRed(grandParent);<br> 3. rotateLeft(grandParent);</td>
</tr>
<tr>
<td align="center">情况3</td>
<td align="left">isRed(parent), isBlack(uncle), uncle == grandParent.left, current == parent.left</td>
<td align="left">1. current = parent;<br> 2. rotateRight(current);<br> 3. 检测 current 是否违背原则并处理</td>
</tr>
<tr>
<td align="center">情况4</td>
<td align="left">isRed(parent), isBlack(uncle), uncle == grandParent.right, current == parent.right</td>
<td align="left">1. current = parent;<br> 2. rotateLeft(current);<br> 3. 检测 current 是否违背原则并处理</td>
</tr>
<tr>
<td align="center">情况5</td>
<td align="left">isRed(parent), isBlack(uncle), uncle == grandParent.right, current == parent.left</td>
<td align="left">1. setBlack(parent);<br> 2. setRed(grandParent);<br> 3. rotateRight(grandParent);</td>
</tr>
</tbody></table>
<pre><code class="java">
    // 插入修正
    private void insertFix(RBTNode&lt;T&gt; node) {
        RBTNode&lt;T&gt; parent;
        RBTNode&lt;T&gt; grandParent;
        while (isRed(parentOf(node))) {
            parent = parentOf(node);
            grandParent = parentOf(parent);
            RBTNode&lt;T&gt; uncle;
            if (parent == grandParent.left) {
                uncle = grandParent.right;
                if (isRed(uncle)) {  // 情况 1
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grandParent);
                    node = grandParent;
                    continue;
                }
                if (isBlack(uncle)) {
                    if (parent.right == node) { // 情况 4
                        node = parent;
                        rotateLeft(grandParent);
                    } else { // 情况 5
                        setBlack(parent);
                        setRed(grandParent);
                        rotateRight(grandParent);
                    }
                }
            } else {
                uncle = grandParent.left;
                if (isRed(uncle)) { // 情况 1
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(grandParent);
                    node = grandParent;
                    continue;
                }
                if (isBlack(uncle)) {
                    if (parent.left == node) { // 情况 2
                        node = parent;
                        rotateRight(node);
                    } else { // 情况 3
                        setBlack(parent);
                        setRed(grandParent);
                        rotateLeft(grandParent);
                    }
                }
            }
        } 
    }   

    // 插入
    public void insert(RBTNode&lt;T&gt; node) {
        if (this.root == null) {
            this.root = node;
        } else {
            int compare = 0;
            RBTNode&lt;T&gt; temp = null;
            RBTNode&lt;T&gt; current = this.root;

            //1. 先查找二叉树, 确定node的插入位置
            while (current != null) {
                temp = current;
                compare = node.getKey().compareTo(current.getKey());
                if (compare &lt; 0) current = current.getLeft(); 
                else current = current.getRight(); 
            }

            node.setParent(temp);
            compare = node.getKey().compareTo(temp.getKey());
            if (compare &lt; 0) temp.setLeft(node);
            else temp.setRight(node);
        } 
        insertFix(node);
        setBlack(root);
    } 
</code></pre>
<h4 id="删除并修正"><a href="#删除并修正" class="headerlink" title="删除并修正"></a>删除并修正</h4><ol>
<li>核心思想: 将被删节点所包含的额外黑色节点(右节点)不断往根节点方向移动并按照情况修正</li>
<li>修正的方法</li>
</ol>
<table>
<thead>
<tr>
<th align="center">情况</th>
<th align="left">现象说明</th>
<th align="left">处理策略</th>
</tr>
</thead>
<tbody><tr>
<td align="center">情况1</td>
<td align="left">isRed(current)&amp;&amp;isBlack(brother) or isRed(brother)&amp;&amp;isBlack(current)</td>
<td align="left">1. setBlack(current);<br> 2. 执行核心思想移动其子节点</td>
</tr>
<tr>
<td align="center">情况2</td>
<td align="left">isBlack(current) isBlack(brother) current==root</td>
<td align="left">执行核心思想移动子节点</td>
</tr>
<tr>
<td align="center">情况3</td>
<td align="left">isBlack(current) isBlack(brother) current!=root</td>
<td align="left">执行下面4中情况</td>
</tr>
<tr>
<td align="center">情况3-1</td>
<td align="left">isRed(brother)</td>
<td align="left">1. setBlack(brother);<br> 2. setRed(parent);<br> 3. rotateLeft(parent);<br> 4. 重新设置current的brother</td>
</tr>
<tr>
<td align="center">情况3-2</td>
<td align="left">isBlack(brother), isBlack(brother.left), isBlack(brother.right)</td>
<td align="left">1. setRed(brother);<br> 2. current = parent</td>
</tr>
<tr>
<td align="center">情况3-3</td>
<td align="left">isBlack(brother), isBlack(brother.right), isRed(brother.left)</td>
<td align="left">1. setBlack(brother.left);<br> 2. setRed(brother);<br> 3. rotateRight(brother);<br> 4. 重新设置current的brother</td>
</tr>
<tr>
<td align="center">情况3-4</td>
<td align="left">isBlack(brother), isRed(brother.right)</td>
<td align="left">1. brother.color = parent.color;<br> 2. setBlack(parent);<br> 3. setBlack(brother.right);<br> 4. rotateLeft(brother);<br> 5. root = x</td>
</tr>
</tbody></table>
<h2 id="完整实现"><a href="#完整实现" class="headerlink" title="完整实现"></a>完整实现</h2><pre><code class="java">public class RBTree&lt;T extends Comparable&lt;T&gt;&gt; {

    private RBTNode&lt;T&gt; root;

    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(RBTNode&lt;T&gt; node) {
        if (node != null) {
            System.out.println(node + &quot; &quot;);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(RBTNode&lt;T&gt; node) {
        if (node != null) {
            inOrder(node.left);
            System.out.println(node.toString());
            inOrder(node.right);
        }
    }

    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(RBTNode&lt;T&gt; node) {
        if (node != null) {
            preOrder(node.left);
            preOrder(node.right);
            System.out.println(node + &quot; &quot;);
        }
    }

    public void insert(T key) {
        insert(new RBTNode&lt;T&gt;(key, null, null, null, false));
    }

    private void insert(RBTNode&lt;T&gt; node) { 
    }

    private RBTNode&lt;T&gt; parentOf(RBTNode&lt;T&gt; x) {
        return (x == null ? null : x.parent);
    }

    private boolean isRed(RBTNode&lt;T&gt; x) {
        if (x == null) return false;
        return !x.isBlack;
    }

    private boolean isBlack(RBTNode&lt;T&gt; x) {
        return (x == null || x.isBlack);
    }

    private void setRed(RBTNode&lt;T&gt; x) {
        if (x != null)
            x.isBlack = false;
    }

    private void setBlack(RBTNode&lt;T&gt; x) {
        if (x != null)
            x.isBlack = true;
    }

    private void insertFix(RBTNode&lt;T&gt; node) { 
    }

    private void rotateRight(RBTNode&lt;T&gt; y) {
    }

    private void rotateLeft(RBTNode&lt;T&gt; x) { 
    }

    public void remove(RBTNode&lt;T&gt; node) {
    }
}

//测试代码
public static void main(String[] args) {
        RBTree&lt;Integer&gt; tree = new RBTree&lt;&gt;();
        int[] arr = new int[]{9, 8, 3, 5, 4, 2, 7, 6, 1};
        for (int item : arr)
            tree.insert(9);
        System.out.println(&quot;前序&quot;);
        tree.preOrder();
        System.out.println(&quot;----------------------&quot;);
        System.out.println(&quot;中序&quot;);
        tree.inOrder();
        System.out.println(&quot;----------------------&quot;);
        System.out.println(&quot;后序&quot;);
        tree.postOrder();
    }

// 前序
// key: 8 B  
// key: 4 R 8 Left 
// key: 2 B 4 Left 
// key: 1 R 2 Left 
// key: 3 R 2 Right 
// key: 6 B 4 Right 
// key: 5 R 6 Left 
// key: 7 R 6 Right 
// key: 9 B 8 Right 
// ----------------------
// 中序
// key: 1 R 2 Left
// key: 2 B 4 Left
// key: 3 R 2 Right
// key: 4 R 8 Left
// key: 5 R 6 Left
// key: 6 B 4 Right
// key: 7 R 6 Right
// key: 8 B 
// key: 9 B 8 Right
// ----------------------
// 后序
// key: 4 R 8 Left 
// key: 2 B 4 Left 
// key: 1 R 2 Left 
// key: 3 R 2 Right 
// key: 6 B 4 Right 
// key: 5 R 6 Left 
// key: 7 R 6 Right 
// key: 9 B 8 Right 
// key: 8 B  </code></pre>
<h2 id="参考文献"><a href="#参考文献" class="headerlink" title="参考文献"></a>参考文献</h2><ol>
<li><a href="https://sandbox.runjs.cn/show/2nngvn8w" target="_blank" rel="noopener">https://sandbox.runjs.cn/show/2nngvn8w</a></li>
<li><a href="http://www.cnblogs.com/skywang12345/p/3624343.html" target="_blank" rel="noopener">http://www.cnblogs.com/skywang12345/p/3624343.html</a></li>
<li><a href="http://www.cnblogs.com/skywang12345/p/3245399.html" target="_blank" rel="noopener">http://www.cnblogs.com/skywang12345/p/3245399.html</a></li>
</ol>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 zhao4xi@126.com </span>
    </div>
</article>



<div class="article_copyright">
    <p><span class="copy-title">文章标题:</span>红黑树的实现原理及应用</p>
    <p><span class="copy-title">文章字数:</span><span class="post-count">2k</span></p>
    <p><span class="copy-title">本文作者:</span><a href="javascript:void(0)" title="Zhaoxi">Zhaoxi</a></p>
    <p><span class="copy-title">发布时间:</span>2018-12-29, 15:12:44</p>
    <p><span class="copy-title">最后更新:</span>2019-09-21, 15:24:34</p>
    <span class="copy-title">原始链接:</span><a class="post-url" href="/zhaoxiwork.gitee.io/2018/12/29/红黑树的实现原理及应用/" title="红黑树的实现原理及应用">https://zhaoxiwork.gitee.io/zhaoxiwork.gitee.io/2018/12/29/红黑树的实现原理及应用/</a>
    <p>
        <span class="copy-title">版权声明:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
    </p>
</div>





    




    </div>
    <div class="copyright">
        <p class="footer-entry">©2016-2019 Zhaoxi</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full"><span class="min "></span></button>
<button class="post-toc-menu"><span class="post-toc-menu-icons"></span></button>
<div class="post-toc"><span class="post-toc-title">目录</span>
    <div class="post-toc-content">

    </div>
</div>
<a class="" id="rocket" href="javascript:void(0)"></a>
    </div>
</div>
<div class="acParent"></div>

</body>
<script src="/js/jquery.pjax.js?v=1.0.1" ></script>

<script src="/js/script.js?v=1.0.1" ></script>
<script>
    var img_resize = 'default';
    /*作者、标签的自动补全*/
    $(function () {
        $('.search').AutoComplete({
            'data': ['#MySQL','#锁','#redis','#lock','#spring','#transaction','#bean scope','#Spring','#tcp','#spring mvc','#ThreadLocal','#http','#https','#ioc','#循环依赖','#aop','#volatile','#Thread Safe','#Collection','#Thread','#Thread Pool','#红黑树',],
            'itemHeight': 20,
            'width': 418
        }).AutoComplete('show');
    })
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $(".post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        

        /*高亮代码块行号*/
        
        $('pre code').each(function(){
            var lines = $(this).text().split('\n').length - 1, widther='';
            if (lines>99) {
                widther = 'widther'
            }
            var $numbering = $('<ul/>').addClass('pre-numbering ' + widther).attr("unselectable","on");
            $(this).addClass('has-numbering ' + widther)
                    .parent()
                    .append($numbering);
            for(var i=1;i<=lines;i++){
                $numbering.append($('<li/>').text(i));
            }
        });
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
    }

    /*打赏页面隐藏与展示*/
    

</script>

<!--加入行号的高亮代码块样式-->

<style>
    pre{
        position: relative;
        margin-bottom: 24px;
        border-radius: 10px;
        border: 1px solid #e2dede;
        background: #FFF;
        overflow: hidden;
    }
    code.has-numbering{
        margin-left: 30px;
    }
    code.has-numbering.widther{
        margin-left: 35px;
    }
    .pre-numbering{
        margin: 0px;
        position: absolute;
        top: 0;
        left: 0;
        width: 20px;
        padding: 0.5em 3px 0.7em 5px;
        border-right: 1px solid #C3CCD0;
        text-align: right;
        color: #AAA;
        background-color: ;
    }
    .pre-numbering.widther {
        width: 35px;
    }
</style>

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
        .nav .hide-list.fullscreen {
            left: 492px
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    
    .post .pjax article .article-entry>ol, .post .pjax article .article-entry>ul, .post .pjax article>ol, .post .pjax article>ul{
        border: #e2dede solid 1px;
        border-radius: 10px;
        padding: 10px 32px 10px 56px;
    }
    .post .pjax article .article-entry li>ol, .post .pjax article .article-entry li>ul,.post .pjax article li>ol, .post .pjax article li>ul{
        padding-top: 5px;
        padding-bottom: 5px;
    }
    .post .pjax article .article-entry>ol>li, .post .pjax article .article-entry>ul>li,.post .pjax article>ol>li, .post .pjax article>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    .post .pjax article .article-entry li>ol>li, .post .pjax article .article-entry li>ul>li,.post .pjax article li>ol>li, .post .pjax article li>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    
    .nav-right:before {
        content: ' ';
        display: block;
        position: absolute;
        left: 0;
        top: 0;
        width: 100%;
        height: 100%;
        opacity: 0.3;
        background: url("https://i.loli.net/2019/07/22/5d3521411f3f169375.png");
        background-repeat: no-repeat;
        background-position: 50% 0;
        -ms-background-size: cover;
        -o-background-size: cover;
        -moz-background-size: cover;
        -webkit-background-size: cover;
        background-size: cover;
    }
    

    
</style>







</html>
